package com.zwj.interview.动态规划;

/**
 * 题目：
 * 输入一个字符串，请问至少需要分割几次才可以使分割出的每个子字符串都是回文？
 * 例如，输入字符串"aaba"，至少需要分割1次，从两个相邻字符'a'中间切一刀将字符串分割成两个回文子字符串"a"和"aba"
 */
public class 分割字符串为回文串的最小次数 {

    /**
     * 假设字符串为S，下标为i的字符为S[i]，下标从j到i的子字符串为S[j..i]。
     * 用f（i）表示从下标为0到i的子字符串S[0..i]的符合条件的最少分割次数。如果字符串的长度是n，那么f（n-1）就是问题的解
     * <p>
     * 如果子字符串S[0..i]本身就是一个回文，那么不需要分割就符合要求，此时f（i）等于0。
     * 如果子字符串S[0..i]不是一个回文，那么对每个下标j（1≤j≤i）逐一判断子字符串S[j..i]是不是回文。
     * 如果是回文，那么这就是一个有效的分割方法，此时的分割次数相当于子字符串S[0..j-1]的分割次数再加1，
     * 因为这是将子字符串S[0..j-1]按照要求分割之后再在S[j-1]和S[j]这两个字符中间再分割一次。
     * 因此，f（i）就是所有符合条件的j对应的f（j-1）的最小值加1
     */
    public int minCut(String s) {
        int len = s.length();
        //isPal用来记录子字符串S[j..i]是不是回文，并将子字符串是否为回文的结果保存在“isPal[j][i]”中
        boolean[][] isPal = new boolean[len][len];
        for (int i = 0; i < len; i++) {
            for (int j = 0; j <= i; j++) {
                char ch1 = s.charAt(i);
                char ch2 = s.charAt(j);
                //判断子字符串S[j..i]是否为回文的标准是字符S[j]和S[i]相同，并且子字符串S[j+1..i-1]也是回文
                if (ch1 == ch2 && (i <= j + 1 || isPal[j + 1][i - 1])) {
                    isPal[j][i] = true;
                }
            }
        }
        int[] dp = new int[len];
        /**
         * 数组dp用来存放f（i）的计算结果，f（i）的计算结果放在数组dp下标为i的位置
         */
        for (int i = 0; i < len; i++) {
            if (isPal[0][i]) {
                //从下标0到i是回文串，那么f(i)=0
                dp[i] = 0;
            } else {
                dp[i] = i;
                for (int j = 1; j <= i; j++) {
                    if (isPal[j][i]) {
                        dp[i] = Math.min(dp[i], dp[j - 1] + 1);
                    }
                }
            }
        }
        return dp[len - 1];

    }
}
